package exam;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 重构队列,height为人的高度,count为排在他前面且身高大于等于他的人数
 *
 * @author shenenlu
 * @date 2021-11-1 18:34
 */
public class RepairQueue {


    public static void main(String[] args) {

        Person[] people = new Person[]{
                new Person(7,0),
                new Person(4,4),
                new Person(7,1),
                new Person(10,0),
                new Person(5,0),
                new Person(6,1),
                new Person(5,2)
        };

        RepairQueue repairQueue = new RepairQueue();
        repairQueue.repair(people);
        Arrays.stream(people).forEach(System.out::println);

    }


    public void repair(Person[] people){
        if( people == null || people.length == 0){
            return;
        }
        Arrays.sort(people, new Comparator<Person>() {
            @Override
            public int compare(Person o1, Person o2) {
                if( o1.count != o2.count){
                    return Integer.compare(o1.count, o2.count);
                }else {
                    return Integer.compare(o1.height, o2.height);
                }
            }
        });

        int needCheckIndex = 0;
        for( int i=0; i< people.length; i++){
            if( people[i].count != 0){
                needCheckIndex = i;
                break;
            }
        }
        for(int i= needCheckIndex; i < people.length; i++){
            int result = checkOrder(people[i], i, people);
            if( result < 0){
                for( int j=0; j < i; j++){
                    Person p = people[i];
                    if( checkOrder(p, j, people) == 0 && p.height < people[j].height){
                        int tempIndex = i;
                        while (tempIndex > j){
                            people[tempIndex] = people[tempIndex-1];
                            people[tempIndex-1] = people[tempIndex-2];
                            tempIndex--;
                        }
                        people[j] = p;
                        needCheckIndex++;
                        break;
                    }
                }
            }else if( result > 0 ){
                Person p = people[i];
                for( int j=i+1; j < people.length; j++){
                    if( checkOrder(p, j, people) == 0 && p.height < people[j].height){
                        int tempIndex = i;
                        while (tempIndex < j){
                            people[tempIndex] = people[tempIndex+1];
                            people[tempIndex+1] = people[tempIndex+2];
                            tempIndex++;
                        }
                        people[j] = p;
                        needCheckIndex++;
                        break;
                    }
                }
            }
        }
    }


    private int checkOrder(Person person, int index, Person[] people) {
        int tallerCount = 0;
        for(int i=0; i<index; i++){
            if(person == people[i]){
                continue;
            }
            if( people[i].height >= person.height){
                tallerCount ++;
            }
        }
        if( person.count < tallerCount){
            return -1;
        }else if( person.count > tallerCount){
            return 1;
        }else {
            return 0;
        }
    }

}


class Person{
    public int height;

    public int count;

    public Person(int height, int count){
        this.height = height;
        this.count = count;
    }

    @Override
    public String toString(){
        return height+","+count;
    }
}
